package com.duing.listnode;

import java.util.List;

// 反转链表
public class ReverseList {

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,3,4,5};
        ListNode node = ListNode.arrayToListNode(arr);
        ListNode.print(node);
        ListNode reverse = reverseList(node);
        ListNode.print(reverse);
    }

    /**
     * 1->2->3->4
     *         head  head.next
     *           3    4
     *           3 <- 4
     *      2 <- 3 <- 4
     * 1 <- 2 <- 3 <- 4
     *
     * 每次处理节点时  都要先获取到下一个节点的反转结果
     * 递归的出口   head==null || head.next==null
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode result = reverseList(head.next);
        ListNode.print(result);
        // 反转的过程
        head.next.next = head;
        // 去掉原有的指向
        head.next = null;
        return result;
    }
}
